#include <cstdio>
#include <iostream>
#include <vector>
#define N 100000
using namespace std;
const long long inf = (long long)(1e18);
int read() {
    char c = 0;
    int sum = 0;
    while (c < '0' || c > '9') c = getchar();
    while ('0' <= c && c <= '9') sum = sum * 10 + c - '0', c = getchar();
    return sum;
}
struct rds {
    int l, r, d;
};
rds dque[N + 1];
int n, q, top, rt[N + 1], maxn[N + 1], lg[N + 1];
long long dp[N + 1];
vector<int> p[N + 1];
struct seg {
    struct node {
        int ls, rs, data;
        long long data2, data3;
    };
    node tree[40 * N + 1];
    int length;
    void push_up(int k) {
        tree[k].data = tree[tree[k].ls].data + tree[tree[k].rs].data,
        tree[k].data2 = tree[tree[k].ls].data2 + tree[tree[k].rs].data2,
        tree[k].data3 = tree[tree[k].ls].data3 + tree[tree[k].rs].data3;
        return;
    }
    int add(int k, int L, int R, int x, int d1, int d2, int d3) {
        int nw = ++length;
        tree[nw] = tree[k];
        if (L == R) {
            tree[nw].data += d1, tree[nw].data2 += d2, tree[nw].data3 += d3;
            return nw;
        }
        int mid = (L + R) >> 1;
        if (x <= mid)
            tree[nw].ls = add(tree[nw].ls, L, mid, x, d1, d2, d3);
        else
            tree[nw].rs = add(tree[nw].rs, mid + 1, R, x, d1, d2, d3);
        push_up(nw);
        return nw;
    }
    long long query(int k, int L, int R, int l, int r, int d1, int d2, int d3) {
        if (!tree[k].data) return 0;
        if (L == l && R == r)
            return 1ll * tree[k].data * d1 + tree[k].data2 * d2 +
                   tree[k].data3 * d3;
        int mid = (L + R) >> 1;
        if (r <= mid)
            return query(tree[k].ls, L, mid, l, r, d1, d2, d3);
        else if (l >= mid + 1)
            return query(tree[k].rs, mid + 1, R, l, r, d1, d2, d3);
        else
            return query(tree[k].ls, L, mid, l, mid, d1, d2, d3) +
                   query(tree[k].rs, mid + 1, R, mid + 1, r, d1, d2, d3);
    }
};
seg T;
long long get_matrix(int l1, int r1, int l2, int r2, int d1, int d2, int d3) {
    return T.query(rt[r1], 1, n, l2, r2, d1, d2, d3) -
           T.query(rt[l1 - 1], 1, n, l2, r2, d1, d2, d3);
}
long long F(int l, int r) {
    if (l > r) return inf;
    long long res = 0;
    res += get_matrix(1, l, r, n, 1, 0, 0);
    res += get_matrix(l, n, 1, r, r - l, 1, -1);
    int mid = (l + r) >> 1;
    res += get_matrix(mid + 1, r, r + 1, n, r + 1, -1, 0);
    res += get_matrix(l + 1, mid, r + 1, n, -l, 1, 0);
    mid = (l + r + 1) >> 1;
    res += get_matrix(1, l - 1, l, mid - 1, -l + 1, 0, 1);
    res += get_matrix(1, l - 1, mid, r - 1, r, 0, -1);
    return dp[l - 1] + res;
}
int main() {
    freopen("block.in", "r", stdin);
    freopen("block.out", "w", stdout);
    int l, r, ps;
    for (int i = 2; i <= N; ++i) lg[i] = lg[i >> 1] + 1;
    n = read() - 1, q = read();
    while (q--) l = read(), r = read() - 1, p[l].push_back(r);
    for (int i = 1; i <= n; ++i) {
        rt[i] = rt[i - 1];
        for (int j = 0; j < p[i].size(); ++j)
            rt[i] = T.add(rt[i], 1, n, p[i][j], 1, i, p[i][j]);
    }
    for (int i = 1; i <= n; ++i) {
        while (top && F(i, dque[top].l) < F(dque[top].d, dque[top].l)) top--;
        if (top && F(i, dque[top].r) < F(dque[top].d, dque[top].r)) {
            ps = dque[top].r;
            for (int j = lg[dque[top].r - dque[top].l]; j >= 0; --j)
                if (ps - (1 << j) > dque[top].l &&
                    F(i, ps - (1 << j)) < F(dque[top].d, ps - (1 << j)))
                    ps -= (1 << j);
            dque[top].r = ps - 1;
        }
        ps = dque[top].r;
        if (ps + 1 <= n) dque[++top] = (rds){ps + 1, n, i};
        ps = 0;
        for (int j = lg[top]; j >= 0; --j)
            if (ps + (1 << j) <= top && dque[ps + (1 << j)].l <= i)
                ps += (1 << j);
        dp[i] = F(dque[ps].d, i);
    }
    printf("%lld\n", dp[n]);
    return 0;
}
